1. Field of Invention
This invention relates to the transmission of data in a constrained binary form serially through an information channel. More particularly this invention relates to a method and apparatus for efficiently transmitting signals sequentially which are free of d.c. bias in a run-length limited encoding scheme.
In the transmission of binary data, such as through a communication link or by recording on a magnetic medium, it is desirable to encode the data to achieve self synchronization and to prevent loss of any information based on the variation in the average or d.c. level of the signal conveying the encoded information. A common method of achieving self synchronization is to provide a minimum of transitions regardless of data content. At the same time, it is also desirable to maintain a controlled time separation between transition so as to avoid inter-symbol interference. A coding scheme in which the length of the symbol is limited is commonly referred to as a run-length limited code.
It is frequently desirable to include synchronization information in a transmission format or serialized data code. In magnetic recording, transitions at a particular time benchmark may be assigned the value 1, and the absence of a transition at a benchmark may be assigned the value 0. The typical detection process consists of detecting for the presence or absence of transitions at the time benchmarks.
In order to provide for the derivation of a properly synchronized clock to establish the benchmarks from the data in the desired transmission format, the transitions must occur frequently enough to provide synchronization pulses for the local clock device. Nevertheless, consecutive transitions must be sufficiently separated in time to limit inter-symbol interference to a level acceptable for reliable detection. Thus, source binary data must be encoded into a constrained encoded data having a coding format which limits the minimum and maximum time between consecutive sequences according to prescribed coding rules.
In many applications it is desirable to eliminate any d.c. signal component from the waveform which results from the transitions according to the data encoding scheme. A d.c. component in a signal waveform will result in a non-zero average value of amplitude and may cause charge accumulation in any a.c. coupling element in a data channel. Elimination of the d.c. component reduces errors in digital detection. In a waveform corresponding to a binary coded sequence, accumulated charge increases by one unit for a positive step and decreases by one unit for a negative step. The accumulated charge at any point in a binary coded sequence is generally defined as the difference between the number of positive and negative transitions.
Coded sequences may be denoted by parameters such as the shortest run length of zeroes between two consecutive transitions or ones, the longest run length of zeroes between any two transitions or ones and the accumulated charge at any digit position in the sequence.
A data encoding method may be viewed as a mapping or binary data into constrained binary sequences, the efficiency of which is the ratio of encoded binary data bits required to express source binary data bits.
What is needed is an encoding scheme for maximizing the efficiency of source binary data encoded into constrained binary sequences wherein the encoded binary sequences are free of d.c. component accumulation.
2. Description of the Prior Art
A common transmission format or data code is described in U.S. Pat. No. 3,108,261 to Miller issued Oct. 22, 1963. The Miller format described therein involves a suppression of any transition occurring at the beginning of one bit interval following an interval containing a transition at its center. The asymmetry of the waveform generated by the Miller constraints introduces undesirable d.c. components into the information channel.
A run-length-limited d.c. free code is described in Patel, U.S. Pat. No. 3,810,111 issued May 7, 1974 and by A. M. Patel in "Zero-modulation Encoding in Magnetic Recording", IBM J.Res. Develop., Volume 19, Number 4 July 1975 Page 366. Patel describes a one-for-one mapping of binary data into a constrained binary sequence which adapts the Miller code to a d.c. free code. Other descriptions of d.c. free run-length-limited codes are found in the following patents: Ouchi, U.S. Pat. No. 3,995,264 issued Nov. 30, 1976; Miller, U.S. Pat. No. 4,027,335 issued May 31, 1977; Miller, U.S. Pat. No. 4,234,897 issued Nov. 18, 1980.
Most of the prior art d.c. free run-length-limited encoding techniques have concentrated on the so-called double frequency codes wherein the code rate is about 0.5, i.e., two code bits represent each data bit, and most prior art schemes employ a complex state sequence algorithm to structure d.c. free codes which contain the necessary run-length-limited constraints. The prior art codes usually start with reference to the shortest word based on the code rate. Consequently, the coding schemes have a limited vocabulary and make up for the limited vocabulary by attempts to achieve other desirable characteristics by increasing the complexity of the encoding algorithm, including a complex look-ahead capability.
In certain applications, particularly in magnetic recording media in which the magnetic coating must be fully saturated, it is desirable to encode data with density ratios of not less than 1.0, that is, an encoding scheme which allows no more than one flux transition per data bit. Under conditions in which flux reversal is not a critical criterion, such as cable transmission or recording on non-saturable media, density ratios less than 1.0 can be tolerated in exchange for a wider detection window. The density ratio is but one constraint imposed upon encoded binary sequences. While this constraint is inherent in the description of many codes, including the examples used herein, this constraint is not necessarily a restriction on the encoding scheme described hereinafter.